package 优先算法.二分查找.点名;

import java.util.HashMap;
import java.util.HashSet;

/**
 * https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/
 */
public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 8};
        System.out.println(so.takeAttendance(arr));
        System.out.println();
    }
}
class Solution {
    //等差求和求解
    public int takeAttendance(int[] records) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < records.length;i++){
            set.add(records[i]);
        }
        for(int i = 0; i < records.length + 1;i++){
            if(!set.contains(i)){
               return i;
            }
        }
        return -1;
    }
}
class Solution3 {
    //等差求和求解
    public int takeAttendance(int[] records) {
        int n = records.length+1;
        int rel = (0+n-1)*n/2;
        for(int i = 0; i < records.length; i++){
            rel-=records[i];
        }
        return rel;
    }
}
class Solution2 {
    //异或求解
    public int takeAttendance(int[] records) {
        int n = records.length+1;
        int rel = 0;
        for(int i=0; i<n; i++){
            rel^= i;
        }
        for(int i=0; i<records.length; i++){
            rel^= records[i];
        }
        return rel;
    }
}
class Solution1 {
    //二分求解
    public int takeAttendance(int[] records) {
        int left = 0,right = records.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(records[mid] == mid){
                left = mid + 1;
            }
            if(records[mid] != mid){
                right = mid;
            }
        }
        if(left == records[left]){
            return left+1;
        }
        return left;
    }
}